The cloning of integrated circuits, today""s crowning example of mass production, proceeds by copying information from a set of masks onto a wafer. The wafer starts as a disk of pure substrate, such as silicon. It is then augmented by a sequence of chemical treatments, each followed by exposure to radiation under a different mask. After this sequence of treatments under masks, a wafer emerges having finished circuitry on it. The wafer need only be cut in order to yield rectangular fragments called dice, or chips. The task is completed as each die is placed and connected into its final resting place.
In all cases, the entirety of the intended electronic circuitry is represented in the masks.
Due to the constant evolution of integrated circuit manufacturing technology, new capabilities arise quickly. For example, a new innovation might require a longer exposure to the radiation than before, introducing an unfortunate side-effect-the wires become thinner, too thin. Rather than redesigning the old integrated circuit, it is often easier just to manipulate the masks, after the fact, thus allowing old designs to continue to work on new technology. In this example, the mask manipulation would consist of fattening all shapes (wires) on the mask(s) involved, all to compensate for the unwanted side effect of shrinkage.
FIG. 1 shows the heart of the mask manipulation task. The given design to be committed to masks, our input, is delivered in what we call design layers, the original design intent 100. Our output, data to make masks, are called mask layers 110. Any other (temporary) layers that come to exist during the transformation from design layers to mask layers are called intermediate layers 120.
In common to all mask manipulation is the need to transform the original design layers into new, mask layers. These transformations consist of fattening and shrinking, along with the Boolean operations: OR, AND, NOT, etc. The Boolean OR operator, for example, proceeds by taking in a pair of corresponding pixels from two layers, performing the Boolean OR to produce the corresponding pixel on the resulting layer. Taken together, these are called layer operations, or Boolean+ operations.
The need for the Boolean manipulations may be seen by this example: Transistors are formed typically at the intersection of two design layers. By ANDing those two design layers together, we find all transistors. If evolving technology came to demand a new mask altogether, to represent just the transistors, we could produce that mask. More likely, the evolution would require a bloat or a shrink of that result.
In fact, today""s available wealth of many metal layers, of great use for routing, is due to an advance that required suddenly a xe2x80x9cminimum average density of metalxe2x80x9d over the masks, even in unused regions. This minimum average density is fortunately solvable by Boolean+ operations, although the number of intermediate layers increases to accommodate this.
All of the details in the integrated circuit design patterns must go through software that implements these Boolean+ operators so as to produce workable masks.
The time required to execute that software can be large (hours). As the gymnastics required to meet the foundry""s requirements increase over time, the complexity of the Boolean+ operators increases. More and more intermediate or temporary layers come to exist, just as we find intermediate results showing up in non-trivial software programs.
A notation consisting of equations may be used to specify the mask manipulations to be performed. The following equation defines a mask layer named Mask_Layerxe2x80x941. The equation ANDs two design layers (X and Y) and then ORs that result with design layer Z:
Mask_Layerxe2x80x941=( X and Y ) or Z 
This equation has one intermediate layer, namely, the result from ANDing X and Y, even though we haven""t given that intermediate layer a name.
Intermediate layers also arise naturally within sets of equations, as one might declare an intermediate layer explicitly, such as in:
Intermediatexe2x80x941=X and Y 
Mask_Layerxe2x80x941=Intermediatexe2x80x941 or Z 
The result, Intermediate xe2x80x941, may now be referenced multiple times in other equations. In fact, intermediate layers are found by taking the layer names appearing on equations"" left-hand sides, excluding mask layers (outputs), and augmenting that with all operations that appear within other operations.
In the conventional art, each layer is represented by a file. The set of Boolean+ operations proceeds one at a time. Each operation reads one or two files as input layers and produces one file as the output layer. The entirety of the design (on the input layers) is read, and a file for the output layer is produced for the entire design.
Because a given file will typically not fit in RAM, the input files read and the output file produced cannot be buffered from one operation to the next, and so the disk I0 is as slow as possible.
output layer may be a finished mask layer or an intermediate layer that will feed a subsequent operation. Notice that all layers, including intermediate layers, reside on disk at some time in the conventional art.
The present invention provides a speed up of the Boolean+ software by avoiding placing intermediate layers on disk. With the number of intermediate layers increasing, these disk access savings may become more significant in the future. In analogy to software optimizing compiler technology, we xe2x80x9ckeep the data in the registersxe2x80x9d and avoid LOADs and STOREs to and from main memory, opening the potential for speedier execution.
The present invention circumvents the disk for intermediate layers by slicing the design into (slightly) overlapping regions, each small enough to fit in main memory. Each region is then processed in its entirety, i.e., all equations executed upon that region, before taking on the next region. Thus all intermediate layers come to exist (in main memory) within one region at a time, and are then discarded before proceeding with the next region. The intermediate layers never go out to the disk. Within each region, temporary layers stay in main memory and may be referenced multiple times, as often occurs in equations, all without consulting the disk.
As a result, the only disk access besides to the original design and to the final output (MEBES) files, is an initial sorting of the design (already necessary for other reasons) that simultaneously places the design polygons in their separate regions.
The objective of the invention is to speed up the Boolean+ software by not placing intermediate layers on disk, which saves disk space, and more significantly, the time of disk access, all in anticipation of an increase in the number intermediate layers. A further objective is to allow such software to run on a multiplicity of inexpensive (uniprocessor) computers, in parallel. These objectives are met by regionalizing the heavily layered data into to regions small enough so that all layers fit in RAM within a region, and so can be treated independently. Another objective is to temper the invention so as to be practical even in the face of very large bloats and shrinks, by trading off large bloats and shrinks for disk residency of some subset of intermediate layers.